#include "LinkList.h"

Status LinkList::InitList(void)
{
    // 创建头结点
    LinkListHead = (LinkNode *)malloc(sizeof(LinkNode));
    if (LinkListHead == nullptr)
        exit(OVERFLOW);

    LinkListHead->next = nullptr;

    return OK;
}

Status LinkList::DestoryList(void)
{
    LinkNode *q;

    while (LinkListHead) {
        q = LinkListHead->next;
        free(LinkListHead);
        LinkListHead = q;
    }

    return OK;
}

Status LinkList::ClearList(void)
{
    LinkNode *p, *q;

    // p指向第一个节点
    p = LinkListHead->next;

    while (p) {
        q = p->next;
        free(p);
        p = q;
    }

    LinkListHead->next = nullptr;

    return OK;
}

Status LinkList::ListEmpty(void)
{
    if (LinkListHead->next == nullptr)
        return OK;
    else
        return FALSE;
}

int LinkList::ListLength(void)
{
    LinkNode *p = LinkListHead->next;
    int count = 0;

    while (p) {
        count++;
        p = p->next;
    }

    return count;
}

/**
 * 获得链表第i个位置的节点
 */
Status LinkList::GetElem(int i, ElemType *e)
{
    LinkNode *p = LinkListHead->next;
    int j = 0;

    while (p && j < i) {
        p = p->next;
        j++;
    }

    if (p == nullptr || j > i)
        return FALSE;

    *e = p->e;

    return OK;
}

int LinkList::LocateElem(ElemType e, Status(*compare)(ElemType, ElemType))
{
    LinkNode *p = LinkListHead->next;
    int i = 0;

    while (p) {
        i++;
        if (compare(e, p->e))
            return i;

        p = p->next;
    }

    return 0;
}

/**
 * 获得cur元素的直接前驱
 */
Status LinkList::PriorElem(ElemType cur, ElemType *prev)
{
    LinkNode *p, *q;

    //指向第一个节点
    p = LinkListHead->next;
    while (p) {
        // q是p的后继节点
        q = p->next;
        if (q->e == cur) {
            *prev = p->e;
            return OK;
        }
        // p向后移动
        p = q;
    }

    return INFEASIBLE;
}

/**
 * 获得cur元素的直接后继
 */
Status LinkList::NextElem(ElemType cur, ElemType *next)
{
    LinkNode *p = LinkListHead->next;

    // p所指向的节点有后继
    while (p->next) {
        if (p->e == cur) {
            *next = p->next->e;
            return OK;
        }
        p = p->next;
    }

    return INFEASIBLE;
}

/**
 * 在第i个位置之前插入元素
 */
Status LinkList::ListInsert(int i, ElemType e)
{
    LinkNode *p = LinkListHead;
    int j = 0;

    while (p && j < i) {
        p = p->next;
        j++;
    }

    if (!p || j > i) {
        return FALSE;
    }

    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->e = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

/**
 * 删除第i个元素
 */
Status LinkList::ListDelete(int i, ElemType *e)
{
    LinkNode *p = LinkListHead;
    int j = 0;

    // 找到待删除元素的i位置的前驱
    while (p->next && j < i) {
        p = p->next;
        j++;
    }

    if (p->next == nullptr || j > i)
        return FALSE;

    LinkNode *q = p->next;
    p->next = q->next;
    *e = q->e;
    free(q);

    return OK;
}

Status LinkList::ListTraverse(void)
{
    LinkNode *p = LinkListHead->next;

    while (p) {
        print(&p->e);
        p = p->next;
    }

    printf("\n");

    return OK;
}

/**
 * 头部插入节点
 */
Status LinkList::ListHeadInsert(ElemType e)
{
    LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));

    node->e = e;

    node->next = LinkListHead->next;
    LinkListHead->next = node;

    return OK;
}
/**
 * 尾部插入节点
 */
Status LinkList::ListTailInsert(ElemType e)
{
    LinkNode *p = LinkListHead;

    while (p->next) {
        p = p->next;
    }

    LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));
    node->e = e;
    node->next = nullptr;

    p->next = node;

    return OK;
}
